package dynamic;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author luo
 * @description
 * @since 2022/7/25 17:42
 */
public class MaximalSquare {
    char[][] matrix;

    @DisplayName("最大正方形")
    @Test
    public void example1() {
        char[][] matrix = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        int maxVal = maximalSquare(matrix);

        Assertions.assertEquals(4, maxVal);
        show(maxVal);
    }

    @Test
    public void example2() {
        char[][] matrix = {
                {'1', '1'},
                {'1', '1'},
        };
        int maxVal = maximalSquare(matrix);
        Assertions.assertEquals(4, maxVal / '1');
        show(maxVal);
    }

    @Test
    public void example3() {
        char[][] matrix = {
                {'1', '1', '0'},
                {'1', '1', '0'},
        };
        int maxVal = maximalSquare(matrix);
        Assertions.assertEquals(4, maxVal / '1');
        show(maxVal);
    }

    @Test
    public void example4() {
        char[][] matrix = {
                {'0', '1', '1'},
                {'0', '1', '1'},
                {'0', '1', '1'},
        };
        int maxVal = maximalSquare(matrix);
        Assertions.assertEquals(4, maxVal / '1');
        show(maxVal);
    }

    @Test
    public void example5() {
        char[][] matrix = {
                {'0', '1', '1', '1'},
                {'0', '1', '1', '1'},
                {'0', '1', '1', '1'},
                {'0', '1', '1', '1'},
        };
        int maxVal = maximalSquare(matrix);
        Assertions.assertEquals(9, maxVal / '1');
        show(maxVal);
    }

    public void show(int maxVal) {
        System.out.println("最大面积是：" + maxVal / '1');
    }

    public int maximalSquare(char[][] matrix) {
        this.matrix = matrix;
        return maximalSquare(0, matrix.length - 1, 0, matrix[0].length - 1);
    }

    private int maximalSquare(int oneDimensionLeft, int oneDimensionRight, int twoDimensionLeft, int twoDimensionRight) {

        if (oneDimensionLeft == oneDimensionRight && twoDimensionLeft == twoDimensionRight) {
            return matrix[oneDimensionLeft][twoDimensionLeft];
        }

        int oneMiddle = (oneDimensionLeft + oneDimensionRight) / 2;
        int twoMiddle = (twoDimensionLeft + twoDimensionRight) / 2;
//        拆解为4个小正方体
        int a1 = maximalSquare(oneDimensionLeft, oneMiddle, twoDimensionLeft, twoMiddle);
        int a2 = maximalSquare(oneDimensionLeft, oneMiddle, twoMiddle + 1, twoDimensionRight);
        int a3 = maximalSquare(oneMiddle + 1, oneDimensionRight, twoDimensionLeft, twoMiddle);
        int a4 = maximalSquare(oneMiddle + 1, oneDimensionRight, twoMiddle + 1, twoDimensionRight);
        int result = a1 == a2 && a2 == a3 && a3 == a4 ? a1 + a2 + a3 + a4 : 0;
        return result;
    }
}
